package com.bruce.algorithm.MaxSum;

/**
 * @author luotuan
 * @Description 最大子序列和问题
 * @create 2020-05-06 16:02
 **/
public class MaxSumTest {
    public static int sum(int[] array) {
        int maxSum = 0;
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum = sum + array[i];
            if (sum > maxSum) {
                maxSum = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
    }

    private static int maxSumRec(int[] a, int left, int right) {
        if (left == right) {
            if (a[left] > 0) {
                return a[left];
            } else {
                return 0;
            }
        }
        int center = (left + right) / 2;
        int maxLeftSum = maxSumRec(a, left, center);
        System.out.println("left="+left+",right="+right+"的左边最大值："+maxLeftSum);
        int maxRightSum = maxSumRec(a, center + 1, right);
        System.out.println("left="+left+",right="+right+"的右边最大值："+maxRightSum);
        int maxLeftBorderSum = 0, lefBorderSum = 0;
        for (int i = center; i >= left; i--) {
            lefBorderSum += a[i];
            if (lefBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = lefBorderSum;
            }
        }
        if(left==0&&right==3){
            System.out.println("测试");
        }
        int maxRightBorderSum = 0, rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }
        System.out.println("left="+left+",right="+right+"的中间左最大值："+maxLeftBorderSum+"，右最大值："+maxRightBorderSum);
        return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
    }

    public static int max3(int a, int b, int c) {
        int max = (a > b) ? a : b;
        return (max > c) ? max : c;
    }

    public static void main(String[] args) {
        int[] array = {-2, 11, -4, 13, -5, -2,-1,2};
        System.out.println(sum(array));
        System.out.println(maxSumRec(array, 0, array.length - 1));
    }
}
